package library;

import java.util.Scanner;

public class KnapSackMultiple {

	//Index [weightleft]
	int[]solution;

	//weight of each item.
	int[] weight;
	//value of each item.
	int[] value;

	//Special for diving for gold
	int w;

	/*
	 * NOTES:
	 * 		handle when num items = 0
	 */

	public KnapSackMultiple() {

		Scanner s = new Scanner(System.in);

		boolean f=true;

		while (s.hasNext()){

			//Print a line between each case
			if(!f)
				System.out.println("");

			f=false;

			//Get the bounds...
			int maxWeight = s.nextInt();

			w = s.nextInt(); //Specific to diving for gold

			int numItems = s.nextInt();

			//Needed for all cases
			setup(numItems,maxWeight);

			//Fill in weights and values
			for (int i =0; i < numItems; i++){

				weight[i]=s.nextInt()*w*3;

				value[i]=s.nextInt();
			}

			//Handle 0 case
			if (numItems==0){

				System.out.println("0\n0");
			}
			else{

				//Solve it, and print the max weight
				System.out.println(solveMultiple());
				//Print the number of solutions
				System.out.println(getNumSolutionsMultiple());
				//Print the weight and value of each item IN THE ORDER THEY WERE ADDED.
				printSolutionMultiple();
			}
		}
	}
	/**
	 * Aux method for getNumSolutionsSingle(item,weightLeft)
	 * @return
	 */
	public int getNumSolutionsMultiple(){
		return getNumSolutionsMultiple(solution.length-1);
	}
	/**
	 * Gets the numbers of items used in the solution.
	 * ONLY USE FOR SOLVE SINGLE
	 * 
	 * @param item The current item number (start from numitems-1)
	 * @param weightLeft The weight left (start from maxweight)
	 * @return The number of items used in solution
	 */
	public int getNumSolutionsMultiple(int weightLeft){
		if (weightLeft==0)
			return 0;
		if (solution[weightLeft]==solution[weightLeft-1])
			return getNumSolutionsMultiple(weightLeft-1);
		else
			for (int i=0; i <value.length;i++)
				if (weight[i]<=weightLeft && solution[weightLeft]==value[i]+solution[weightLeft-weight[i]]){
					return getNumSolutionsMultiple(weightLeft-weight[i]);
				}
		return 0;
	}
	/**
	 * Aux method for printSolutionSingle(item,weight)
	 */
	public void printSolutionMultiple(){
		printSolutionMultiple(solution.length-1);
	}
	/**
	 * Prints the weight and value of each node used in solution
	 * @param item
	 * @param weightLeft
	 */
	public void printSolutionMultiple(int weightLeft){
		if (weightLeft==0)
			return;
		if (solution[weightLeft]==solution[weightLeft-1])
			printSolutionMultiple(weightLeft-1);
		else
			for (int i=0; i <value.length;i++)
				if (weight[i]<=weightLeft && solution[weightLeft]==value[i]+solution[weightLeft-weight[i]]){
					printSolutionMultiple(weightLeft-weight[i]);
					System.out.println(weight[i]+" "+value[i]);
					return;
				}
	}
	/**
	 * Setup the arrays
	 * This is here so we don't accidently do this wrong (like getting an index wrong)
	 * @param numItems	The total number of items.
	 * @param maxWeight The maximum possible weight
	 */
	public void setup(int numItems, int maxWeight){

		solution = new int[maxWeight+1];
		weight=new int[numItems];
		value=new int[numItems];

		for (int i=0;i<numItems;i++){
			for (int j=0;j<maxWeight+1;j++){
				solution[j]=-1;
			}
		}
	}
	/**
	 * Aux method for solvemultiple(int weightleft)
	 * @return
	 */
	public int solveMultiple(){
		return solve(solution.length);
	}
	/**
	 * ONLY WORKS FOR POSITIVE WEIGHTS
	 * MULTIPLE INTANCES OF EACH ITEM ALLOWED
	 * USES SOLUTIONM[]
	 * 
	 * solution must be all -1's to start
	 * start with solve(total_weight)
	 * 
	 * @param weightLeft
	 * @return
	 */
	public int solve(int weightLeft){
		if(solution[weightLeft]==-1){
			//without item.
			int valuewithout=solve(weightLeft-1);
			//with and item
			int valuewith=0;
			//Go through all items
			for (int i =0; i < value.length;i++){
				valuewith = Math.max(valuewith, value[i]+solve(weightLeft-weight[i]));
			}
			solution[weightLeft] = Math.max(valuewithout, valuewith);
		}
		return solution[weightLeft];
	}

	public static void main(String[] args) {
		new KnapSackMultiple();
	}

}
